package cn.hy.today;

import java.util.Arrays;

class Solution_410 {


    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        // 前缀和，preSum[i] = sum[0..i)
        int[] preSum = new int[n + 1];
        preSum[0] = 0;
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        // 前0- i区间被 分成k段，各自和的最大值的最小值为 dp[i][k]
        int[][] dp = new int[n][m + 1];
        dp[0][0] = 0;
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        //分割数为1 ，状态值为前缀和
        for (int i = 0; i <= n; i++) {
            dp[i][1] = preSum[i + 1];
        }

        // 从分割 成2 段开始
        for (int k = 2; k <= m; k++) {
            // i 的 k-1 开始计算
            for (int i = k - 1; i < n; i++) {
                // j 表示第 k - 1 个区间的最后一个元素的下标，最小值为 k - 2，最大值为 len - 2（最后一个区间至少有 1 个元素）
                for (int j = k - 2; j < i; j++) {
                    dp[i][k] = Math.min(dp[i][k], Math.max(dp[j][k - 1], preSum[i + 1] - preSum[j + 1]));
                }
            }
        }
        return dp[n - 1][m];
    }
}